package com.lw.leetcode.other.b;

/**
 * Created with IntelliJ IDEA.
 * 343. 整数拆分
 * 剑指 Offer 14- I. 剪绳子
 * 剑指 Offer 14- II. 剪绳子 II
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/29 16:25
 */
public class IntegerBreak {

    public static void main(String[] args) {
        IntegerBreak test = new IntegerBreak();

        // 516560652
        // 516560652
        int item = 1;
        for (int i = 0; i < 17; i++) {
            item *= 3;
        }
        System.out.println(item * 4);
    }

    public int cuttingRope(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        int a = n / 3;
        int b = n % 3;

        if (b == 1) {
            a--;
            b = 4;
        } else if (b == 0) {
            b = 1;
        }

        long item = 1L;
        for (int i = 0; i < a; i++) {
            item *= 3;
            item %= 1000000007;
        }
        return (int) (item * b % 1000000007);
    }

    public int integerBreak(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        if (n == 4) {
            return 4;
        }
        if (n == 5) {
            return 6;
        }
        if (n == 6) {
            return 9;
        }
        int[] arr = new int[n - 1];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 4;
        arr[3] = 6;
        arr[4] = 9;
        int max = 1;
        int b;
        for (int i = 7; i <= n; i++) {

            b = i >> 1;
            for (int j = 2; j <= b; j++) {
                max = Math.max((arr[i - j - 2]) * j, max);
            }
            arr[i - 2] = max;
            max = 1;
        }
        return arr[n - 2];
    }
}
